/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/build-post-office-ii
   @Language: C++
   @Datetime: 19-06-13 11:03
   */

class Solution {
	void bfs(vector<vector<int> > &grid, int row, int col){
		unordered_set<long> visit;
		queue<pair<long,long> > que;
		int rows=grid.size(), cols=grid[0].size(), dist=0;
		for(que.push({row,col}); que.size(); ++dist){
			for(int size=que.size(); size--; que.pop()){
				const auto &p=que.front();
				if(p.first<0||p.first>=rows||p.second<0||p.second>=cols) continue;
				if((p.first==row && p.second==col) || grid[p.first][p.second]>=0){
					if(visit.count((p.first<<32)|p.second)) continue;
					visit.insert((p.first<<32)|p.second);
					grid[p.first][p.second]+=dist;
					que.push({p.first+1,p.second});
					que.push({p.first-1,p.second});
					que.push({p.first,p.second+1});
					que.push({p.first,p.second-1});
				}
			}
		}
		for(long i=0; i<grid.size(); ++i)
			for(long j=0; j<grid[i].size(); ++j)
				if(grid[i][j]>=0 && visit.count((i<<32)|j)==0) grid[i][j]=-2;
	}
public:
	/**
	 * @param grid: a 2D grid
	 * @return: An integer
	 */
	int shortestDistance(vector<vector<int> > &grid) {
		// write your code here
		int dist=-1;
		for(int i=0; i<grid.size(); ++i)
			for(int j=0; j<grid[i].size(); ++j)
				grid[i][j]=-grid[i][j];
		for(int i=0; i<grid.size(); ++i)
			for(int j=0; j<grid[i].size(); ++j)
				if(grid[i][j]==-1) bfs(grid,i,j);
		for(int i=0; i<grid.size(); ++i)
			for(int j=0; j<grid[i].size(); ++j)
				if(grid[i][j]>0) dist=min(dist<0?INT_MAX:dist,grid[i][j]);
		return dist;
	}
};
